<html>
<head><meta charset="utf-8"><title>unwinding in rayon&#x27;s sort · t-compiler/wg-llvm · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/index.html">t-compiler/wg-llvm</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html">unwinding in rayon&#x27;s sort</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="204919066"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/204919066" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> frederic wagner <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#204919066">(Jul 24 2020 at 14:05)</a>:</h4>
<p>hi everyone,<br>
i've been  testing rayon's slice par_sort algorithm a bit. (by the way, this is my first post here, so i hope i am doing it right)</p>
<p>there is a huge difference of performances when turning on 'panic="abort"' in cargo.<br>
I'm sorting a slice of random integers.<br>
if i unwind i get a lot of extra branches and a huge jump in mispredicted branches. (10%)<br>
if i abort less branches and not many mispredictions (2.7%)</p>
<p>testing code is here.<br>
<a href="https://is.gd/DkkBy8">https://is.gd/DkkBy8</a> (needs rayon and rand)</p>
<p>we can see the effects instantly with perf (under linux).<br>
it as a noticeable performance effect on my desktop machine and very strong impact (almost x2 acceleration) on a server machine.</p>
<p>perf tells me the branch misses events come from this code inside rayon (src/slice/mergesort.rs):</p>
<div class="codehilite"><pre><span></span><code><span class="w">        </span><span class="k">while</span><span class="w"> </span><span class="n">s</span><span class="p">.</span><span class="n">left_start</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">s</span><span class="p">.</span><span class="n">left_end</span><span class="w"> </span><span class="o">&amp;&amp;</span><span class="w"> </span><span class="n">s</span><span class="p">.</span><span class="n">right_start</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">s</span><span class="p">.</span><span class="n">right_end</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="c1">// Consume the lesser side.</span>
<span class="w">            </span><span class="c1">// If equal, prefer the left run to maintain stability.</span>
<span class="w">            </span><span class="kd">let</span><span class="w"> </span><span class="n">to_copy</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">is_less</span><span class="p">(</span><span class="o">&amp;*</span><span class="n">s</span><span class="p">.</span><span class="n">right_start</span><span class="p">,</span><span class="w"> </span><span class="o">&amp;*</span><span class="n">s</span><span class="p">.</span><span class="n">left_start</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="n">get_and_increment</span><span class="p">(</span><span class="o">&amp;</span><span class="k">mut</span><span class="w"> </span><span class="n">s</span><span class="p">.</span><span class="n">right_start</span><span class="p">)</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="n">get_and_increment</span><span class="p">(</span><span class="o">&amp;</span><span class="k">mut</span><span class="w"> </span><span class="n">s</span><span class="p">.</span><span class="n">left_start</span><span class="p">)</span><span class="w"></span>
<span class="w">            </span><span class="p">};</span><span class="w"></span>
<span class="w">            </span><span class="n">ptr</span>::<span class="n">copy_nonoverlapping</span><span class="p">(</span><span class="n">to_copy</span><span class="p">,</span><span class="w"> </span><span class="n">get_and_increment</span><span class="p">(</span><span class="o">&amp;</span><span class="k">mut</span><span class="w"> </span><span class="n">s</span><span class="p">.</span><span class="n">dest</span><span class="p">),</span><span class="w"> </span><span class="mi">1</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
</code></pre></div>


<p>i'm not extra fluent in assembly but it seems to me the fast version uses conditional moves while the slow version does not.</p>
<p>I'm not sure what you can do with that but since the sort is an important algorithm it might be worth to try something.</p>
<p>if anything i'd be happy to know what is going on.</p>



<a name="204920063"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/204920063" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#204920063">(Jul 24 2020 at 14:12)</a>:</h4>
<p>I was thinking, <span class="user-mention" data-user-id="324777">@frederic wagner</span>, if we wanted to try and eliminate the integer comparison question, maybe you can test a version that is specialized to integer types, and not written generically?</p>



<a name="204920140"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/204920140" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#204920140">(Jul 24 2020 at 14:13)</a>:</h4>
<p>I'm working from the hypothesis of course that is something to do with the compiler assuming unwinding can occur and inhibiting an optimization.</p>



<a name="204920265"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/204920265" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#204920265">(Jul 24 2020 at 14:14)</a>:</h4>
<p>The other thing to do would be to dump some of the intermediate LLVM IR but I don't know as much about that, i.e., I'm not sure which would be the best IR to examine.</p>



<a name="204920343"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/204920343" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> frederic wagner <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#204920343">(Jul 24 2020 at 14:14)</a>:</h4>
<p>oh it's a good idea to have an integer version. it can be done quite fast. i'll take a look.</p>



<a name="204934266"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/204934266" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#204934266">(Jul 24 2020 at 16:06)</a>:</h4>
<p>If the issue really is branches vs <code>cmov</code>, then this is a very unfortunate situation because there's no good way to force (or even reliably persuade) LLVM to use <code>cmov</code>s -- for good reasons, but still. Thus, even if panic=abort helps today, any change to the surrounding code or LLVM passes or rustc's codegen could potentially turn it back to branchy code. I've seen talk of this (convincing the compiler to emit cmovs when beneficial) being a problem in the C/C++ world too.</p>



<a name="204990302"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/204990302" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> frederic wagner <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#204990302">(Jul 25 2020 at 06:03)</a>:</h4>
<p>ok, so i switched the whole code to integers and it does not change anything.<br>
i also removed the call to copy_non_overlapping</p>



<a name="207509260"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/207509260" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#207509260">(Aug 20 2020 at 10:43)</a>:</h4>
<p><span class="user-mention" data-user-id="324777">@frederic wagner</span> very curious, did you ever figure anything else out here?</p>



<a name="207517812"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/207517812" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> frederic wagner <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#207517812">(Aug 20 2020 at 12:46)</a>:</h4>
<p>hi, i did a few more simplifications to the code but with no change in behavior. i'm actually not too sure to understand how exceptions are handled by the compiler. i thought panic-able functions calls would get an added check on return and functions which cannot panic would not. but in this case i don't see what could panic. time was running short so we put it aside. i'm not sure i can reach this deep in the compiler without  a heavy time investment.</p>



<a name="207518160"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/207518160" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#207518160">(Aug 20 2020 at 12:50)</a>:</h4>
<p>Unwinding is handled by having a side table that defines how to restore registers and to what place to jump to when the instruction pointer is at a certain place during unwinding. There is no cost when not unwinding except for inhibiting optimizations that would prevent restoring values necessary to run the cleanup code.</p>



<a name="207542350"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/unwinding%20in%20rayon%27s%20sort/near/207542350" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/unwinding.20in.20rayon&#x27;s.20sort.html#207542350">(Aug 20 2020 at 16:21)</a>:</h4>
<p>It's the exact same mechanism as C++ exceptions, although that equivalence is not ABI-guaranteed</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>